package lecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 56. 合并区间的复杂版本
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 * 示例 2：
 *
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出：[[1,2],[3,10],[12,16]]
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 */
public class 插入区间57 {

    public static void main(String[] args) {
        int[][] nums = {{1,3},{6,9}};
        int[] newInterval = {2,5};
//        int[][] nums1 = insert1(nums,newInterval);
//        System.out.println(Arrays.deepToString(nums1));
        int[][] nums2 = insert2(nums,newInterval);
        System.out.println(Arrays.deepToString(nums2));
    }

    /**
     * 方法一、排序法
     * 先将两个数组合并，然后排序，然后遍历排序后的数组，判断是否有重叠的区间，有的话合并，没有的话插入到合适的位置。
     */
    public static int[][] insert1(int[][] intervals, int[] newInterval) {
        // 将newInterval添加到intervals中并排序
        intervals = merge(intervals, newInterval);
        //返回结果集
        List<int[]> res = new ArrayList<>();
        for (int[] interval : intervals) {
            int index = res.size();
            if (index > 0 && res.get(index - 1 )[1] >= interval[0]) {
                res.set(index - 1, new int[]{res.get(index - 1)[0], Math.max(res.get(index - 1)[1], interval[1])});
            }else {
                res.add(interval);
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    /**
     * 合并两个数组并排序
     */
    public static int[][] merge(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length+1][2];
        for (int i = 0; i < intervals.length; i++) {
            res[i] = intervals[i];
        }
        res[res.length - 1] = newInterval;
        Arrays.sort(res, (p, q) -> p[0] - q[0]);
        return res;
    }


    /**
     * 方法二、贪心算法
     * 主要是将intervals分成三部分：定义index
     * 1. 第一个区间，intervals[0] < newInterval[0]
     * 2. 第二个区间，intervals[0]与newInterval[0]重叠
     * 3. 第三个区间，intervals[index]到结束部分
     */
    public static int[][] insert2(int[][] intervals, int[] newInterval) {
        //返回结果集
        LinkedList<int[]> res = new LinkedList<>();
        int index = 0;
        //处理第一部分 interval[0] < newInterval[0]
        for (int[] interval : intervals) {
            if (interval[0] < newInterval[0]) {
                res.add(interval);
                index++;
            }else {
                break;
            }
        }
        //处理第二部分 合并intervals[0]< newInterval[0] 最后一个区间
        if (!res.isEmpty() && res.getLast()[1] >= newInterval[0]) {
            res.getLast()[1] = Math.max(res.getLast()[1], newInterval[1]);
        }else {
            res.add(newInterval);
        }

        //处理第三部分 合并intervals[index]到结束部分
        for (int i = index; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (!res.isEmpty() && res.getLast()[1] >= interval[0]) {
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], interval[1]);
            }else {
                res.add(interval);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
